Question I: Coin Change Problem

This question illustrates the Change problem and the use of Dynamic programming.

(a) Write down the running complexity ($O$ -notation) in terms of M, d of the two coin change algorithms RecursiveChange(M,c,d) and DPChange(M,c,d) as mentioned in the lecture slides. Explain your answer.

The running complexity of RecursiveChange(M,c,d) is in $O(d^M)$ The running complexity of DPChange(M,c,d) is in $O(Md)$.

(b) Given the denominations 1, 3, and 4, what is the minimum number of coins needed to make change for a given value of 11? Find this out by writing down each step of the dynamic programming algorithm introduced in the lecture.

For the dynamic programming algorithm the minimum number of coins needed is computed for every value up to the value which is asked for. The results are stored in a list and used for the computation of higher values. Therefore first you initalize the list with the needed coins with the single element 0 as for the value 0, no coins are needed to make change. Then for every value up to the value which has been asked for you append a new element to the list which is set to infinity. Then you you go through all you denominations and check if the denomination is smaller than your value. If this is true you can test if the number of needed coins for the given denomination would be smaller than the already tested denominations. If so you can update the number of needed coins for the values which is computed at this step.

For the value 11 and the denominations 1,3,4 the algorithm does the following with the list of needed coins.

[0] 
[0, inf] 
[0, 1] 
[0, 1, inf] 
[0, 1, 2] 
[0, 1, 2, inf] 
[0, 1, 2, 3] 
[0, 1, 2, 1] 
[0, 1, 2, 1, inf]
[0, 1, 2, 1, 2]
[0, 1, 2, 1, 1]
[0, 1, 2, 1, 1, inf]
[0, 1, 2, 1, 1, 2]
[0, 1, 2, 1, 1, 2, inf]
[0, 1, 2, 1, 1, 2, 3]
[0, 1, 2, 1, 1, 2, 2]
[0, 1, 2, 1, 1, 2, 2, inf]
[0, 1, 2, 1, 1, 2, 2, 3]
[0, 1, 2, 1, 1, 2, 2, 2]
[0, 1, 2, 1, 1, 2, 2, 2, inf]
[0, 1, 2, 1, 1, 2, 2, 2, 3]
[0, 1, 2, 1, 1, 2, 2, 2, 2]
[0, 1, 2, 1, 1, 2, 2, 2, 2, inf]
[0, 1, 2, 1, 1, 2, 2, 2, 2, 3]
[0, 1, 2, 1, 1, 2, 2, 2, 2, 3, inf]
[0, 1, 2, 1, 1, 2, 2, 2, 2, 3, 4]
[0, 1, 2, 1, 1, 2, 2, 2, 2, 3, 3]
[0, 1, 2, 1, 1, 2, 2, 2, 2, 3, 3, inf]
[0, 1, 2, 1, 1, 2, 2, 2, 2, 3, 3, 4]
[0, 1, 2, 1, 1, 2, 2, 2, 2, 3, 3, 3]



In [1]:

    
def DPChange(M,c,d):
    import math
    best_num_coins = [0]
    for m in range(1,M+1):
        best_num_coins.append(math.inf)
        for i in range(0,d):
            if m >= c[i]:
                if best_num_coins[m-c[i]] +1 < best_num_coins[m]:
                    best_num_coins[m] = best_num_coins[m-c[i]] + 1
    
    return best_num_coins[M]



In [2]:

    
DPChange(11,[1,3,4], 3)









    Out[2]:





3

Question II: Manhattan Tourist Problem

Longest Path Problem : The goal of this problem is to use the directed graph as in Fig. 1 and to find the longest path from E1 to D6.

(a) Using the approach of the Manhattan Tourist Problem, use dynamic programming to find the length of the longest path



In [112]:

    
import numpy as np

n = -np.inf
                #      E1 M1 G1 D1 D2 M2 G2 D3 M3 G3 D4 E2 E3 D5 D6
adjacency = np.matrix([[n, 0, 0, 0, n, n, n, n, n, n, n, n, n, n, n],  #E                      
                      [n, n, 0, 20, n, 20, 20, n, n, n, n, n, n, n, n],#M1
                      [n, n, n, n, n, 15, 15, n, n, n, n, n, n, n, n], #G1
                      [n, n, n, n, 10, n, 10, n, n, n, n, n, n, n, n], #D1
                      [n, n, n, n, n, n, n, 15, n, n, n, n, n, n, n],  #D2
                      [n, n, n, n, n, n, n, n, 20, 20, 20, n, n, n, n],#M2
                      [n, n, n, n, n, n, n, n, n, 20, n, n, n, n, n],  #G2
                      [n, n, n, n, n, n, n, n, 20, n, 20, n, n, n, n], #D3
                      [n, n, n, n, n, n, n, n, n, n, n, 15, n, n, n],  #M3
                      [n, n, n, n, n, n, n, n, n, n, n, 5, n, n, n],   #G3
                      [n, n, n, n, n, n, n, n, n, n, n, 10, n, n, n],  #D4
                      [n, n, n, n, n, n, n, n, n, n, n, n, 45, n, n],  #E2
                      [n, n, n, n, n, n, n, n, n, n, n, n, n, 10, n],  #E3
                      [n, n, n, n, n, n, n, n, n, n, n, n, n, n, 5],   #D5
                      [n, n, n, n, n, n, n, n, n, n, n, n, n, n, n]])  #D6


def MTP(adj):
    '''
    This function returns the length of thlongest path of a 
    directed acyclic graph. Therefore it can solve the Manhattan 
    Tourist Problem.
    
    This function works only on adjacency matrices
    in which the nodes are ordered topologically.
    '''
    import numpy as np
    score = {0:0}
    for node in range(1,adj.shape[0]):
        possibilities = []
        for in_edge in range(adj.shape[1]):
            if adj[in_edge,node] >= 0:
                possibilities.append(adj[in_edge,node] + score[in_edge])
        score[node] = max(possibilities)   
    return score[adj.shape[1]-1]

MTP(adjacency)









    Out[112]:





140.0

(b) Using backtracking calculate the longest path

The longest path is E1->M1->D1->D2->D3->M3->E2->E3->D5->D6